package com.hanxiaozhang.sort;

import com.hanxiaozhang.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈快速排序〉
 *
 * @author hanxinghua
 * @create 2021/9/12
 * @since 1.0.0
 */
public class FastSort {

    public static void main(String[] args) {
        int[] array1 = {2, 4, 6, 8, 11, 4, 2, 5, 7, 9};
        fastSort1(array1, 0, array1.length - 1);
        System.out.println(Arrays.toString(array1));

        int[] array2 = {2, 4, 6, 8, 11, 4, 2, 5, 7, 9};
        fastSort2(array2, 0, array1.length - 1);
        System.out.println(Arrays.toString(array2));

        int[] array3 = {2, 4, 6, 8, 11, 4, 2, 5, 7, 9};
        fastSort3(array3, 0, array1.length - 1);
        System.out.println(Arrays.toString(array3));

    }

    /**
     * 在arr[L..R]范围上，进行快速排序的过程：
     * 1）用arr[R]对该范围做partition，<= arr[R]的数在左部分并且保证arr[R]最后来到左部分的最后一个位置，记为M； <= arr[R]的数在右部分（arr[M+1..R]）
     * 2）对arr[L..M-1]进行快速排序(递归)
     * 3）对arr[M+1..R]进行快速排序(递归)
     * 因为每一次partition都会搞定一个数的位置且不会再变动，所以排序能完成
     *
     * @param array
     * @param L
     * @param R
     */
    public static void fastSort1(int[] array, int L, int R) {
        if (L >= R) {
            return;
        }
        int mid = FastTopic.partition_2(array, L, R);
        fastSort1(array, L, mid - 1);
        fastSort1(array, mid + 1, R);
    }


    /**
     * 在arr[L..R]范围上，进行快速排序的过程：
     * 1）用arr[R]对该范围做hollandFlag，< arr[R]的数在左部分，== arr[R]的数中间，>arr[R]的数在右部分。假设== arr[R]的数所在范围是[a,b]
     * 2）对arr[L..a-1]进行快速排序(递归)
     * 3）对arr[b+1..R]进行快速排序(递归)
     * 因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成
     *
     * @param arr
     * @param L
     * @param R
     */
    public static void fastSort2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] equalArea = FastTopic.hollandFlag(arr, L, R);
        fastSort2(arr, L, equalArea[0] - 1);
        fastSort2(arr, equalArea[1] + 1, R);
    }


    /**
     * 快速排序3.0(随机快排+荷兰国旗技巧优化)：
     * 在arr[L..R]范围上，进行快速排序的过程：
     * 1）在这个范围上，随机选一个数记为num，
     * 2）用num对该范围做hollandFlag，< num的数在左部分，== num的数中间，>num的数在右部分。假设== num的数所在范围是[a,b]
     * 3）对arr[L..a-1]进行快速排序(递归)
     * 4）对arr[b+1..R]进行快速排序(递归)
     * 因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成
     *
     * @param arr
     * @param L
     * @param R
     */
    public static void fastSort3(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // 随机选择一个数，跟R位置交换，R位置是需要比较的目标数
        AlgorithmUtil.swap_1(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = FastTopic.hollandFlag(arr, L, R);
        fastSort3(arr, L, equalArea[0] - 1);
        fastSort3(arr, equalArea[1] + 1, R);

    }


}
